package 回溯;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * todo
 *
 * @author songZiHao
 * @version 1.0.0
 * @ClassName 长度为n的开心字符串中字典序第k小的字符串1415.java
 * @createTime 2023年03月08日 18:05:00
 */
public class 长度为n的开心字符串中字典序第k小的字符串1415 {

	public static void main(String[] args) {
		System.out.println(getHappyString(1, 3));
	}

	static List<String> result = new ArrayList<>();

	static char[] chars = new char[] {'a', 'b', 'c'};

	public static String getHappyString(int n, int k) {
		backTrace(n, 0, 'z');
		if (result.size() >= k) {
			return result.get(k - 1);
		}
		return "";
	}

	static LinkedList<Character> tempList = new LinkedList<>();

	public static void backTrace(int n, int cur, char prv) {
		//结束条件，长度满足
		if (cur == n) {
			StringBuilder sb = new StringBuilder();
			for (Character character : tempList) {
				sb.append(character);
			}
			result.add(sb.toString());
			return;
		}
		//循环字符
		for (int i = 0; i < 3; i++) {
			//这个字符如果用掉了，需要跳过
			char temp = prv;
			if (prv != 'z' && chars[i] == temp) {
				continue;
			}
			prv = chars[i];
			tempList.add(prv);
			backTrace(n, cur + 1, prv);
			tempList.removeLast();
			prv = temp;
		}
	}
}
